<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        let arr = [8,6,34,53,87,4,44,0,65]
        function buble(arg){
            let temp = null;
            for(let i=0;i<arg.length;i++){
                for(let j=0;j<arg.length-1-i;j++){
                    if(arg[i]>arg[j]){
                         temp = arg[i]
                         arg[i] = arg[j]
                         arg[j] = temp
                    }
                }
            }
            console.log(arg);
        }
        buble(arr)

        // 插入排序
        function insert(arr){
            for(let i=1;i<arr.length;i++){
                let j = i-1
                if(arr[i]<arr[j]){
                    let temp = arr[i]
                    while(j>=0 && temp<arr[j]){
                        arr[j+1] = arr[j];
                        j--
                    }
                    arr[j+1] = temp
                }
                
            }
            return arr
        }
        console.log(insert(arr))

        // 插入排序

        function insertTop(arr){
            for(let i=1;i<arr.length;i++){
               for(let j=i;j>0;j--){
                   //为了找合适的位置插入；
                   if(arr[j]<arr[j-1]){
                     [arr[j],arr[j-1]] = [arr[j-1],arr[j]]
                   }else{
                       break
                   }
               }
            }
            return arr
        }
        console.time('insertTop')
        console.log('插入排序',insertTop(arr))
        console.timeEnd('insertTop')
        //快速排序
        //先来一版，空间复杂的少一些的
        function quickSort(arr){
            if(arr.length <=1){
                return arr
            }
            let left=[];
            let right=[];
            let flag = arr.shift()
            for(let i=0;i<arr.length;i++){
                if(arr[i]<flag){
                    left.push(arr[i])
                }else{
                    right.push(arr[i])
                }
            }
            return quickSort(left).concat(flag,quickSort(right))
        }
        console.log(quickSort(arr))

        //原地快排；
        function quickSort1(arr,low=0,high=arr.length-1){
            if(low == high){
                return arr
            }
            let left=low
            let right = high
            let flag = arr[left]
            while(left<right){
                //从右边尝试找比flag小的，比flag大，right左移
                if(left<right && flag<=arr[right]){
                    right--
                }
                arr[left] = arr[right]

                if(left<right && flag>=arr[left]){
                    left++
                }
                arr[right] = arr[left]
                arr[left] = flag
                quickSort1(arr,low,left-1)
                quickSort1(arr,low+1,high)
                return arr
            }
            
            
        }
        console.log(quickSort1(arr))
    </script>
</body>
</html>